#include "linearList.h"
using namespace std;

// 初始化顺序表
sequenceList::sequenceList(const int& capacity, const int& initSize, float arr[]) {
    maxCapcity = capacity;
    curNumberOfItem = initSize;
    // 动态分配内存
    myList = new float[maxCapcity]; 
    // 初始化数组
    for (int i = 0; i < curNumberOfItem; i++) {
        myList[i] = arr[i];
    }
}
// 销毁顺序表
sequenceList::~sequenceList() {
    delete[] myList; // 释放动态分配的内存
}
// 添加元素
bool sequenceList::addItem(const float& item) {
    //若顺序表满，则无法添加
    if (curNumberOfItem >= maxCapcity) {
        return false; 
    }
    myList[curNumberOfItem++] = item;
    return true;
}
// 插入元素
bool sequenceList::insertItem(const int& index, const float& item) {
     // 索引越界或顺序表满
    if (index < 0 || index > curNumberOfItem || curNumberOfItem >= maxCapcity) {
        return false; // 索引越界或顺序表满
    }
    // 移动元素，以腾出插入位置
    for (int i = curNumberOfItem; i > index; i--) {
        myList[i] = myList[i - 1];
    }
    // 插入新元素
    myList[index] = item; 
    curNumberOfItem++;
    return true;
}
// 删除元素
int sequenceList::deleteItem(const float& item) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) {
            // 找到元素并删除
            for (int j = i; j < curNumberOfItem - 1; j++) {
                myList[j] = myList[j + 1];
            }
            // 更新当前元素个数
            curNumberOfItem--; 
            // 返回被删除位置
            return i; 
        }
    }
    // 找不到元素
    return -1;
}
// 查找元素（按序号）
bool sequenceList::locate(const int& index, float& val) {
    if (index < 0 || index >= curNumberOfItem) {
        // 索引越界
        return false; 
    }
    val = myList[index]; 
    return true;
}
// 查找元素（按值）
int sequenceList::locate(const float& item) {
    for (int i = 0; i < curNumberOfItem; i++) {
        if (myList[i] == item) {
            // 返回找到的位置
            return i; 
        }
    }
    // 找不到
    return -1;
}

// 倒序排列元素
void sequenceList::reverse() {
    for (int i = 0; i < curNumberOfItem / 2; i++) {
        float temp = myList[i];
        myList[i] = myList[curNumberOfItem - 1 - i];
        myList[curNumberOfItem - 1 - i] = temp;
    }
}

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}



listNode::listNode(float nodeData, listNode *succ) {
    data = nodeData;
    next = succ;
}

listNode::~listNode(){}

// 链表类定义
linkList::linkList() 
    : firstNode(NULL), curNode(NULL), lastNode(NULL), listSize(0) {}

// 带参构造函数，根据给定的数组初始化链表
linkList::linkList(const int& size, float arr[]) {
    // 创建链表的第一个节点
    firstNode = new listNode();
    lastNode = firstNode;  // 初始化最后一个节点为第一个节点
    listSize = 0;  // 初始化链表大小为0
    // 遍历输入数组，将数组元素插入到链表中
    for (int i = 0; i < size; ++i) {
        lastNode->next = new listNode(arr[i]);  // 创建新节点并连接到链表
        lastNode = lastNode->next;               // 移动到链表的最后节点
        ++listSize;                               // 增加链表大小计数
    }
}

// 析构函数，释放链表的内存
linkList::~linkList() {
    listNode* temp;
    // 遍历链表并删除每个节点以防止内存泄漏
    while (firstNode != NULL) {
        temp = firstNode;           // 临时保存当前节点
        firstNode = firstNode->next; // 移动到下一个节点
        delete temp;                // 删除当前节点
    }
}

//头插法
bool linkList::headInsertItem(const float& item) {
    listNode* newNode = new listNode(item, firstNode->next); // 创建新节点
    firstNode->next = newNode;  // 更新头部指向新节点
    if (listSize == 0) {
        lastNode = newNode;      // 如果链表之前为空，则更新最后一个节点
    }
    ++listSize;                   // 增加链表大小计数
    return true;                 // 插入成功
}

//尾插法
bool linkList::tailInsertItem(const float& item) {
    listNode* newNode = new listNode(item); // 创建新节点
    if (listSize == 0) {
        firstNode->next = newNode; // 如果链表为空，头指针指向新节点
        lastNode = newNode;        // 更新最后一个节点
    } else {
        lastNode->next = newNode;  // 否则，将新节点添加到链表的末尾
        lastNode = newNode;        // 更新最后一个节点
    }
    ++listSize;                   // 增加链表大小计数
    return true;                 // 插入成功
}

// 指定位置插入元素
int linkList::insertItem(const int& index, const float& item) {
    if (index < 0 || index > listSize) { // 检查索引是否有效
        return -1;                      // 索引无效，返回 -1
    }
    listNode* newNode = new listNode(item); // 创建新节点
    listNode* temp = firstNode; // 从头节点开始遍历
    for (int i = 0; i < index; ++i) {
        temp = temp->next; // 移动到插入点前一个节点
    }
    newNode->next = temp->next; // 新节点指向当前位置的后继节点
    temp->next = newNode;        // 当前节点指向新节点
    if (index == listSize) {
        lastNode = newNode;      // 如果是插入到链表尾部，更新最后一个节点
    }
    ++listSize;                  // 增加链表大小计数
    return index;               // 返回插入的位置
}

//删除元素
int linkList::deleteItem(const float& item) {
    listNode* temp = firstNode; // 从头节点开始遍历
    listNode* prev = NULL;     // 追踪前一个节点
    int index = -1;            // 初始化索引为 -1
    while (temp->next != NULL) { // 遍历直到链表末尾
        if (temp->next->data == item) { // 找到匹配项
            prev = temp; // 记录前一个节点
            temp = temp->next; // 移动到要删除的节点
            prev->next = temp->next; // 连接前一个节点和后一个节点
            if (temp == lastNode) {
                lastNode = prev; // 如果删除的是最后一个节点，更新最后一个节点
            }
            delete temp; // 删除节点
            --listSize;  // 减少链表大小计数
            index = prev - firstNode; // 计算节点的索引
            break; // 找到并删除后，退出循环
        }
        temp = temp->next; // 移动到下一个节点
    }
    return index; 
}

//查找元素（按序号找）
bool linkList::locate(const int& index, float& val) {
    if (index < 0 || index >= listSize) { // 检查索引是否有效
        return false; // 索引无效，返回 false
    }
    listNode* temp = firstNode->next; // 从第一个有效节点开始
    for (int i = 0; i < index; ++i) {
        temp = temp->next; // 移动到指定索引
    }
    val = temp->data; // 返回该索引位置的值
    return true; // 返回 true，表示找到值
}

// 查找元素（按值找）
int linkList::locate(const float& item) {
    listNode* temp = firstNode->next; // 从第一个有效节点开始
    int index = 0; // 初始化索引
    while (temp != NULL) { // 遍历链表
        if (temp->data == item) { // 找到匹配项
            return index; // 返回索引
        }
        temp = temp->next; // 移动到下一个节点
        ++index; // 增加索引
    }
    return -1; // 如果未找到，返回 -1
}

//递增排序
void linkList::ascendingOrder() {
    if (listSize < 2) { // 如果链表中元素少于两个，不需要排序
        return;
    }
    bool swapped;
    do {
        swapped = false; // 每次循环开始前标志设为 false
        listNode* p = firstNode->next; // 从第一个有效节点开始
        while (p->next != NULL) { // 遍历链表
            if (p->data > p->next->data) { // 进行相邻节点的比较
                std::swap(p->data, p->next->data); // 如果顺序错误，交换节点数据
                swapped = true; // 标记发生了交换
            }
            p = p->next; // 移动到下一个节点
        }
    } while (swapped); // 如果没有交换，表明已排序完成
}

// 反转链表
void linkList::reverse() {
    listNode *prev = NULL, *current = firstNode->next, *next = NULL;
    lastNode = firstNode->next; // 更新最后一个节点为当前头节点
    while (current != NULL) { // 遍历链表
        next = current->next; // 临时保存下一个节点
        current->next = prev; // 反转当前节点的指向
        prev = current; // 移动前指针
        current = next; // 移动当前节点指针
    }
    firstNode->next = prev; // 更新头指针为反转后的链表头
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}





void merge(linkList& A, linkList& B) {
    // 指向A链表的当前节点
    listNode* aCur = A.firstNode->next;
    // 指向B链表的当前节点
    listNode* bCur = B.firstNode->next;
    // 指向A链表的最后一个节点
    listNode* aLast = A.firstNode;
    // 当两个链表都没有遍历完时
    while (aCur != NULL && bCur != NULL) {
        if (aCur->data <= bCur->data) { // 如果A链表的当前节点值小于等于B链表的当前节点值
            aLast->next = aCur;        // 将A链表的当前节点插入到结果链表
            aCur = aCur->next;         // 移动A链表的当前节点
        } else {                        
            aLast->next = bCur;        // 将B链表的当前节点插入到结果链表
            bCur = bCur->next;         // 移动B链表的当前节点
        }
        aLast = aLast->next;           // 更新A链表的最后一个节点
    }
    // 如果A链表还有剩余节点，将它们添加到结果链表的末尾
    if (aCur != NULL) {
        aLast->next = aCur;
    }
    // 如果B链表还有剩余节点，将它们添加到结果链表的末尾
    if (bCur != NULL) {
        aLast->next = bCur;
    }
    // 更新A链表的最后一个节点和链表大小
    while (aLast->next != NULL) {
        aLast = aLast->next;
    }
    A.lastNode = aLast;
    A.listSize = A.listSize + B.listSize;
    A.reverse();
}